\documentclass[%
    %draft,
    %submission,
    %compressed,
    a4paper,
    %12pt,
    10pt,
    final,
    %technote,
    %internal,
    %submitted,
    %inpress,
    %reprint,
    %titlepage,
    notitlepage,
    %anonymous,
    narroweqnarray,
    inline,
    oneside,
    %invited,
    %conference
    article
    ]{ieee}

%\documentclass[a4paper,11pt]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage{float}
\floatstyle{boxed} 
\usepackage{subfig}
\usepackage{epsfig}
\usepackage{epstopdf}
\usepackage{epstopdf}

\newcommand{\latexiie}{\LaTeX2{\Large$_\varepsilon$}}

\begin{document}

\title[]{
	Trabajo Práctico 4\\
	Algoritmos Genéticos}

\author{
     Luciano Mangiarotti (I.T.B.A),
\and Federico Santos (I.T.B.A),
\and Jimena Pose (I.T.B.A) \\ \\ }

\maketitle

\section{Introducci\'on}

\noindent Habitualmente, los perceptrones multicapa con aprendizaje supervisado se entrenan utilizando el algoritmo \textit{back-propagation}. \\

\noindent El objetivo de este trabajo práctico es utilizar otro enfoque, basado en la utilización de un algoritmo genético para el entrenamiento de la red neuronal.\\

\noindent Se utilizan los operadores genéticos \textit{cruce} y \textit{mutación}. El cruce fue implementado de cuatro formas diferentes: Clásico, Múltiple, Uniforme y Anular. En cuanto a la mutación, se utiliza la clásica y la no uniforme.\\

\noindent Para la selección y el reemplazo de los individuos en cada generación se utilizan los siguientes métodos: Elite, Ruleta, Universal, Boltzman, Elite+Ruleta y Elite+Boltzman.\\

\noindent En la Sección II se explica el problema a resolver. En la Sección III se explica la representación elegida para los individuos. Se analiza también la fidelidad de los mismos. \\

\noindent En la Sección IV se detallan las consideraciones realizadas durante la implementación. Por ultimo, en la Sección V se muestran los resultados junto con sus respectivas conclusiones.

\section{Problema a resolver}

\noindent Se dispone de un conjunto de puntos $(x,y)$ y de los valores correspondientes a una función $f(x,y)=z$. Se eligen $50$ valores como patrones para entrenar a la red. La cantidad elegida se debe a que es un número con el que se logró, de manera experimental, analizar satisfactoriamente la performance de la red. \\

\noindent La Figura \ref{fig:grafico1} muestra la representación de estos datos en el plano, mientras que la Figura \ref{fig:grafico2} muestra los datos en el espacio. A partir de este \textit{dataset}, se quiere obtener una red que memorice los patrones con el menor error posible.\\

\section{Representación de los individuos}

\noindent La representación de los individuos es clave a la hora de resolver problemas con algoritmos genéticos.\\

\noindent Un perceptrón multicapa está conformado por un conjunto de pesos que determinan la magnitud de las conexiones entre las neuronas de las distintas capas. \\

\noindent De esta forma, resulta natural considerar a cada peso de la red como un \textit{gen}. \\

\noindent Cada individuo representa una red, donde cada \textit{alelo} corresponde al valor que tiene el peso de la conexión entre dos neuronas determinadas y el \textit{locus} identifica dicha conexión.\\

\noindent Así se forma un vector con los pesos de las conexiones para todas las capas de la red, que corresponde al individuo codificado.\\

\noindent Por último, se analiza la fidelidad de la representación propuesta, teniendo en cuenta las cinco propiedades que determinan si una representación es fiel:\\

\begin{itemize}

\item Completitud: Una red neuronal consiste en un conjunto de pesos, asignados a las distintas conexiones entre las neuronas. En la
representación propuesta se puede almacenar cualquiera de estos pesos y conocer la conexión a la que corresponde. Por este motivo, se puede decir que la representación es completa.\\

\item Coherencia: La representación es coherente porque cualquier combinación de cromosomas que se puede representar corresponde a una red neuronal válida. \\

\item Uniformidad: Cada red está formada por un conjunto específico de pesos. Dos redes son iguales, si todos sus pesos son iguales. Por este motivo, cada red tiene una sola codificación en esta representación.\\

\item Sencillez: Es muy fácil codificar y decodificar un fenotipo, simplemente se tiene que hacer la conversión de las matrices que
almacenan los pesos de la red a vector y viceversa.\\

\item Localidad: Cada cambio en un cromosoma produce un cambio local en el individuo decodificado. En particular, dicho cambio corresponde al cambio de un peso de la red. Cuando se cambia un peso en una red, el comportamiento de la misma no cambia drásticamente. Este concepto está estrechamente ligado a la robustez de las redes neuronales. \\

\end{itemize}

\noindent Teniendo en cuenta que la representación elegida cumple las cinco propiedades enumeradas, se puede decir que la codificación es fiel.

\subsection*{Función de aptitud}

\noindent La función de aptitud utilizada para evaluar el \textit{fitness} está basada en el error cuadrático medio, ya que consiste en una métrica muy utilizada para medir la performance de las redes neuronales. \\

\noindent En particular, se usa la negación de dicho error ya que el objetivo del algoritmo genético es maximizar el \textit{fitness} de los individuos. \\

\noindent Como el error cuadrático medio es un valor positivo, al negarlo siempre da un valor negativo. Cuando este valor se acerca a cero, el \textit{fitness} es mejor, ya que el error de la red es menor. \\

\section{Consideraciones de implementación}

\noindent La arquitectura de red que se utiliza es $[12 - 7 -1]$ con dos entradas. Consta de dos capas ocultas con 12 y 7 neuronas respectivamente y una unidad de salida. \\

\noindent Experimentalmente, se determinó que para poblaciones con mas de 30 individuos no se logra una mejoría relevante en los resultados, razón por la cual no se justifica el mayor esfuerzo computacional necesario. \\

\noindent Por este motivo, en las pruebas realizadas, la población siempre está formada por 30 individuos. La inicialización de los mismos se realiza a partir de valores reales aleatorios seleccionados dentro del rango $[-0.5 \hspace{1px} ; \hspace{1px} 0.5]$. \\

\noindent Otro parámetro relevante, es la brecha generacional o \textit{generation gap}. La misma consiste en el porcentaje de la población que se desea reemplazar en cada generación. A partir de este porcentaje, se deduce la cantidad de individuos que se deben seleccionar para la reproducción.\\

\noindent Todos los individuos que se generan en dicha reproducción van a formar parte de la población en la nueva generación. El resto de los individuos de la nueva generación se seleccionan, utilizando alguno de los criterios mencionados, de la población anterior.\\

\noindent Dado que la probabilidad de cruce puede ser menor que uno, existe la posibilidad de que la cantidad total de individuos reemplazada entre dos generaciones sea levemente menor a la indicada por la brecha generacional.\\

\noindent Experimentalmente, se decidió utilizar un valor de 0.7, lo que equivaldría a reemplazar el 70\% de la población en cada generación.\\

\noindent En cuanto a los operadores genéticos, resulta importante explicar cómo se seleccionaron los nuevos alelos en la mutación. \\

\noindent A la hora de mutar un individuo, se recorre cada uno de sus alelos y con una cierta probabilidad se determina si el mismo se muta o no. \\

\noindent En caso de que corresponda mutarlo se decidió realizar el reemplazo por un valor \textit{random} seleccionado entre el mínimo y máximo valor de los \textit{alelos} de dicho individuo. \\

\noindent El objetivo de esto es que el random devuelva un valor que esté dentro de los márgenes de valores que maneja la red neuronal, ya que si se selecciona un valor \textit{random} sin ninguna restricción podría seleccionarse un valor que perjudique la performance de la red. 

\subsection*{Refinamiento con back-propagation}

\noindent Además de los operadores genéticos mencionados más arriba, también se realiza un refinamiento con el algoritmo de \textit{back-propagation}. \\

\noindent Esto tiene como objetivo mejorar el \textit{fitness} de los individuos. La mejora se realiza en cada generación por cada individuo, con una probabilidad del 10\%. \\

\noindent El mismo consiste en 100 iteraciones \textit{feed-forward} e implementa la mejora del \textit{momentum} con $\alpha = 0.1$. \\

\section{Resultados y Conclusiones}

\noindent En esta sección se desarrollan distintas pruebas modificando parámetros a partir de una configuración inicial para poder comparar los resultados obtenidos. \\

\noindent En la Tabla \ref{tab:parametrosfijos} se listan los parámetros que permanecerán fijos en todas las pruebas. El motivo de la elección de los valores mostrados en la tabla se debe a que son valores típicos de uso para los correspondientes parámetros, y experimentalmente hemos logrado resultados satisfactorios con los mismos.

\begin{table}[h]
	\centering
    	\begin{tabular}{c c}
    		\hline \\
		Individuos en la población & 30 \\
		Brecha generacional $G$ & 0.7 \\
		Temperatura (Boltzman) & 1 \\
		Individuos seleccionados por \textit{Elite} & 10 \\
		Probabilidad de mutación & 0.01 \\
		Probabilidad de cruce & 0.95 \\
		Probabilidad de \textit{back-propagation} & 0.1 \\
		Pasos de \textit{back-propagation} & 100 \\
		Máxima cantidad de generaciones & 300 \\ \\
		\hline
	\end{tabular}
	\caption{Parámetros que permanecen fijos.}
	\label{tab:parametrosfijos}
\end{table}

\noindent A continuación, se presentan los resultados obtenidos junto con sus correspondientes conclusiones. Debido a que los resultados presentan cierto grado de aleatoriedad, se muestra en cada tabla la mejor de tres ejecuciones.

\subsection*{Primera Prueba: Métodos de cruce}

\noindent En este apartado, se busca comparar los distintos métodos de cruce y analizar los resultados obtenidos a partir de los mismos. Como se observa en la Tabla \ref{tab:tabla1}, los resultados son satisfactorios para los cuatro métodos de cruce. \\

\noindent Utilizando el método de cruce uniforme, los resultados encontrados no son tan buenos como con los otros tres. \\

\noindent Esto puede deberse a que dicho método cruza alelos individualmente con determinada probabilidad, en vez de cruzar bloques de los mismos, lo que genera sucesores con mayor variación.

\subsection*{Segunda Prueba: Métodos de mutación}

\noindent Como se puede apreciar en la Tabla \ref{tab:tabla2}, los resultados obtenidos con ambos métodos de mutación también son satisfactorios.\\

\noindent Es importante destacar, que utilizando la mutación no uniforme se obtiene un \textit{fitness} promedio muy similar al \textit{fitness} del mejor individuo. \\

\noindent Evidentemente, el \textit{fitness} de la totalidad de los individuos de la población es muy cercano al del mejor individuo. Esto denota, que el \textit{fitness} de la totalidad de los individuos mejora con el correr de las generaciones. \\

\noindent Esto se debe a que la probabilidad de mutación se decrementa a lo largo de las generaciones y luego de muchas generaciones la misma se vuelve casi nula. \\

\noindent Lo que provoca que los nuevos individuos se generen a partir de la cruza y el refinamiento de \textit{back-propagation}, por lo que no se corre el riesgo de que la mutación empeore el \textit{fitness} de los nuevos individuos.

\subsection*{Tercera Prueba: Métodos de selección y reemplazo}

\noindent En la Tabla \ref{tab:tabla3} se pueden ver los resultados variando a ruleta el método de selección en un caso, y el de reemplazo en otro.\\

\noindent Se eligió ruleta para realizar la comparación ya que no selecciona ningún individuo por \textit{Elite}, como lo hacen \textit{Elite+Ruleta} y \textit{Elite+Boltzman}. A su vez, se trata de un método se selección proporcional al igual que \textit{Universal} y \textit{Boltzman}.\\

\noindent En el caso en el que se utiliza \textit{Ruleta} como método de selección, puede darse el caso que los individuos con mejor \textit{fitness} no se seleccionen para la reproducción, a diferencia de los métodos que seleccionan individuos por \textit{Elite}. Por lo tanto, los individuos que vayan a reproducirse para generar los nuevos sucesores no van a ser los mejores de la población.\\

\noindent De acuerdo con lo expresado anteriormente, se observó que el mejor \textit{fitness} cambió solamente dos veces durante 250 generaciones. El individuo con mejor \textit{fitness} se mantuvo, ya que el método de reemplazo era \textit{Elite+Boltzman}. \\

\noindent Cuando se utiliza \textit{ruleta} como método de reemplazo, se observa que el mejor \textit{fitness} no siempre se mantiene o mejora. Esto genera una diferencia con los métodos elitistas para seleccionar los individuos a reemplazar. \\

\noindent En particular, se observa cierto fenómeno oscilatorio en el mejor \textit{fitness} de la red a lo largo de las generaciones. Esto se debe a que no siempre se elige el individuo con mejor \textit{fitness} en el reemplazo.

\subsection*{Cuarta Prueba: Métodos de corte}

\noindent En las tres pruebas anteriores, se utilizó como criterio de corte la máxima cantidad de generaciones. En particular, se muestran los resultados obtenidos luego de exactamente 300 generaciones. \\

\noindent Otro de los métodos de corte implementados, y que se presentan en esta prueba, es el corte por \textit{estructura}. Es un método enfocado a la calidad, que consiste en observar el porcentaje de repetición de individuos que hay en la población.\\

\noindent En caso de que el porcentaje de individuos iguales supere un 60\%, se considera que la población no va a evolucionar hacia un mejor resultado. Este porcentaje fue determinado de manera experimental. \\

\noindent Por otro lado, se presentan resultados usando otro método de corte enfocado a la calidad. El corte por \textit{contenido} consiste en observar los cambios sobre el mejor \textit{fitness} de la población. En caso de que dicho valor no mejore durante 10 generaciones, la ejecución finaliza. Dicha cantidad de generaciones se determinó experimentalmente. \\

\noindent Por último, se analiza un método de corte de \textit{entorno al óptimo}. El mismo consiste en finalizar la ejecución una vez que se alcanzó un valor de \textit{fitness} determinado, el cual se considera suficiente de acuerdo a las características del problema. En este caso, dicho valor es parametrizable y se usa $-0.05$ para los resultados presentados. \\

\noindent En la Tabla \ref{tab:tabla4} se observan los resultados obtenidos usando los distintos criterios de corte, tanto el que corta por máxima cantidad de generaciones como los cortes enfocados a calidad. \\

\noindent Se puede apreciar que la cantidad de generaciones necesarias fue menor cuando se utilizaron métodos de corte enfocados a calidad. \\

\noindent En dicha tabla se observa que los resultados obtenidos con \textit{estructura}, \textit{contenido} y \textit{entorno al óptimo} cortan a una cantidad de generaciones menor que 300, ya que detectan que en la población es improbable que se generen individuos con mejor \textit{fitness} que los actuales, ni un resultado más satisfactorio que el obtenido.

\subsection*{Comentarios finales}

\noindent Para finalizar, se puede decir que la utilización de un método mixto tanto para la selección como para el reemplazo produjo un resultado más satisfactorio que si se utilizaba un método no mixto, debido a que se aprovechan las características de ambos tipos de método.\\

\noindent Con respecto a los métodos de corte, se concluye que los métodos enfocados a la calidad son los recomendables cuando se tiene una idea anticipada de aquello que se quiere lograr o al menos del funcionamiento de lo que se está ejecutando.\\

\noindent Inicialmente, puede llegar a ser recomendable ejecutar el algoritmo por una cantidad de generaciones máxima y comprender a fondo los aspectos del mismo para posteriormente poder aplicar cortes enfocados a la calidad. \\


% Tablas

\begin{table*}
	\centering
    	\begin{tabular}{c c c c c c}
    		\hline
    		\hline
		\multirow {2} {*} {\textbf{Parámetros}} & \multicolumn{4}{c}{\textbf{Configuración}} \\
		& Base & 1 & 2 & 3 \\
		\hline
		\hline
		Método de corte & Máx. Gen. & Máx. Gen. & Máx. Gen. & Máx. Gen. \\
		Método de selección & Elite+Boltzman & Elite+Boltzman & Elite+Boltzman & Elite+Boltzman \\
		Método de cruce & Clásico & Múltiple & Uniforme & Anular \\
		Método de mutación & Clásico & Clásico & Clásico & Clásico \\
		Método de reemplazo & Elite+Boltzman & Elite+Boltzman & Elite+Boltzman & Elite+Boltzman \\
		\hline
		\hline
		Generaciones & 300 & 300 & 300 & 300 \\
		Mejor \textit{fitness} de la red & -0.0351479 & -0.0355763 & -0.0707056 & -0.0392524 \\
		\textit{Fitness} promedio de la red & -0.524712 & -2.18468 & -2.94812 & -2.70788 \\
		\hline
		\hline
	\end{tabular}
	\caption{Resultados obtenidos con distintos métodos de cruce.}
	\label{tab:tabla1}
\end{table*}

\begin{table*}
	\centering
    	\begin{tabular}{c c c c c c}
    		\hline
    		\hline
		\multirow {2} {*} {\textbf{Parámetros}} & \multicolumn{2}{c}{\textbf{Configuración}} \\
		& Base & 1 \\
		\hline
		\hline
		Método de corte & Máx. Gen. & Máx. Gen. \\
		Método de selección & Elite+Boltzman & Elite+Boltzman \\
		Método de cruce & Clásico & Clásico \\
		Método de mutación & Clásico & No Uniforme \\
		Método de reemplazo & Elite+Boltzman & Elite+Boltzman \\
		\hline
		\hline
		Generaciones & 300 & 300 \\
		Mejor \textit{fitness} de la red & -0.0351479 & -0.0541291 \\
		\textit{Fitness} promedio de la red & -0.524712 & -0.0554994 \\
		\hline
		\hline
	\end{tabular}
	\caption{Resultados obtenidos con distintos métodos de mutación.}
	\label{tab:tabla2}
\end{table*}

\begin{table*}
	\centering
    	\begin{tabular}{c c c c c c}
    		\hline
    		\hline
		\multirow {2} {*} {\textbf{Parámetros}} & \multicolumn{3}{c}{\textbf{Configuración}} \\
		& Base & 1 & 2\\
		\hline
		\hline
		Método de corte & Máx. Gen. & Máx. Gen. & Máx. Gen. \\
		Método de selección & Elite+Boltzman & Ruleta & Elite+Boltzman \\
		Método de cruce & Clásico & Clásico & Clásico \\
		Método de mutación & Clásico & Clásico & Clásico \\
		Método de reemplazo & Elite+Boltzman & Elite+Boltzman & Ruleta \\
		\hline
		\hline
		Generaciones & 300 & 300 & 300 \\
		Mejor \textit{fitness} de la red & -0.0351479 & -0.228254 & -0.0162073 \\
		\textit{Fitness} promedio de la red & -0.524712 & -17.5014 & -11.7319 \\
		\hline
		\hline
	\end{tabular}
	\caption{Resultados obtenidos con distintos métodos de selección y reemplazo.}
	\label{tab:tabla3}
\end{table*}

\begin{table*}
	\centering
    	\begin{tabular}{c c c c c c}
    		\hline
    		\hline
		\multirow {2} {*} {\textbf{Parámetros}} & \multicolumn{4}{c}{\textbf{Configuración}} \\
		& Base & 1 & 2 & 3 \\
		\hline
		\hline
		Método de corte & Máx. Gen. & Estructura & Contenido & Ent. Óptimo \\
		\textit{Fitness} deseado & -- & -- & -- & -0.05 \\
		Método de selección & Elite+Boltzman & Elite+Boltzman & Elite+Boltzman & Elite+Boltzman \\
		Método de cruce & Clásico & Clásico & Clásico & Clásico \\
		Método de mutación & Clásico & Clásico & Clásico & Clásico \\
		Método de reemplazo & Elite+Boltzman & Elite+Boltzman & Elite+Boltzman & Elite+Boltzman \\
		\hline
		\hline
		Generaciones & 300 & 34 & 122 & 269 \\
		Mejor \textit{fitness} de la red & -0.0351479 & --0.0614495 & -0.0542797 & -0.049212 \\
		\textit{Fitness} promedio de la red & -0.524712 & -0.547427 & -1.29048 & -1.88311 \\
		\hline
		\hline
	\end{tabular}
	\caption{Resultados obtenidos con distintos métodos de corte.}
	\label{tab:tabla4}
\end{table*}

% Figuras

\begin{figure*}
        \centering
		\includegraphics[scale=0.6]{grafico1.png}
        \caption[center]{Puntos que forman el conjunto de entrenamiento graficados en el plano.}
       \label{fig:grafico1}
\end{figure*}

\begin{figure*}
        \centering
		\includegraphics[scale=0.6]{grafico2.png}
        \caption[center]{Puntos que forman el conjunto de entrenamiento graficados en el espacio.}
       \label{fig:grafico2}
\end{figure*}


\end{document}